//!@Author: DengLibin
//!@Date: Create in 2024-01-21 11:26:49
//!@Description: 链表
//! RefCell 允许在不使用 unsafe 代码的情况下，获取内部数据的可变引用。
//! 这在 Rust 的所有权和借用规则中是不允许的，因为这些规则要求在任何时候，对同一数据的可变引用只能有一个
//! ，而 RefCell 通过运行时检查来确保这一规则不被违反。

use std::{
    cell::RefCell,
    fmt::Display,
    rc::Rc
};

// 链表节点(单)
#[derive(Debug)]
struct Node<T: Display> {
    val: Option<T>,
    //前一个结点
    pre: Option<Rc<RefCell<Node<T>>>>,
    //后一个节点
    next: Option<Rc<RefCell<Node<T>>>>,
}

//实现drop
impl<D: Display> Drop for Node<D> {
    fn drop(&mut self) {
        print!("销毁节点");
        if let Some(v) = &self.val {
            println!("{}", v);
        }else {
            println!();
        }

    }
}
impl<D: Display> Node<D> {
    fn show(&self) {
        if let Some(v) = &self.val {
            print!("{},", v);
        } else {
            print!("None,")
        }
    }
}
//链表 双链表 会有循环引用（前一个节点引用后一个节点，后一个节点又引用前一个节点，造成Rc计数永远不可能为0，有内存溢出风险）
pub struct LinkedList<T: Display> {
    head: Option<Rc<RefCell<Node<T>>>>,
    tail: Option<Rc<RefCell<Node<T>>>>,
    size: usize,
}

//销毁链表，手动解开节点间的循环引用，释放节点内存
impl<D: Display> Drop for LinkedList<D> {
    ///@Author: DengLibin
    ///@Date: Create in 2024-01-21 18:37:17
    ///@Description: 销毁链表
    fn drop(&mut self) {

        //取出节点引用，销毁节点
        //取出头节点
        let mut node = self.head.take();
        //取出对尾节点的引用
        self.tail.take(); 
        while node.is_some() {
            if let Some(n) = node {
                n.borrow_mut().pre.take(); //取出前一个节点
                node = n.borrow_mut().next.take();//取出后一个节点
            }
        }
        println!();

       println!("销毁链表");
    }
}

impl<D> LinkedList<D>
where
    D: Display,
{
    // 新建链表
    fn new() -> Self {
        LinkedList {
            head: None,
            tail: None,
            size: 0,
        }
    }
    //头部添加
    fn insert_head(&mut self, val: D) {
        print!("添加元素:{}", val);
        //新节点
        let new_node = Node {
            val: Some(val),
            pre: None,
            next: None,
        };
        //引用计数
        let head_rc = Rc::new(RefCell::new(new_node));
        if self.size == 0 {
            self.head = Some(head_rc.clone());
            println!("引用计数:{}", Rc::strong_count(&head_rc));
            self.tail = Some(head_rc)
        } else {
            //原来的头部节点
            let h = self.head.take();
            if let Some(n) = h {
                n.borrow_mut().pre = Some(head_rc.clone()); //前一个节点
                head_rc.borrow_mut().next = Some(n);
            }
            println!("引用计数:{}", Rc::strong_count(&head_rc));
            self.head = Some(head_rc);
        }

        self.size += 1;
    }

    //尾部添加
    fn insert_last(&mut self, val: D) {
        print!("添加元素:{}", val);
        let new_node = Node {
            val: Some(val),
            pre: None,
            next: None,
        };
        let head_rc = Rc::new(RefCell::new(new_node));
        if self.size == 0 {
            self.head = Some(head_rc.clone());
            println!("引用计数:{}", Rc::strong_count(&head_rc));
            self.tail = Some(head_rc)
        } else {
            let t = self.tail.take();
            if let Some(tail) = t {
                tail.borrow_mut().next = Some(head_rc.clone());
                head_rc.borrow_mut().pre = Some(tail);
                //更新尾部
                println!("引用计数:{}", Rc::strong_count(&head_rc));
                self.tail = Some(head_rc);
            }
        }

        self.size += 1;
    }
    //移除最后一个
    fn remove_last(&mut self) -> Option<D> {
        if self.size == 0 {
            return None;
        }
        //获取最后一个元素
        let tail = self.tail.take();

        if let Some(t) = tail {
            //新的尾部的为当前尾部的前一个
            self.tail = t.borrow_mut().pre.take();
            if let Some(new_tail) = self.tail.as_ref() {
                //尾部节点的下一个节点设置为None
                new_tail.borrow_mut().next.take();
            }
            self.size -= 1;
            if self.size == 0 {
                //空了
                self.head.take();
            }
            let t = Rc::into_inner(t);
            if let Some(v) = t {
                let mut node = v.into_inner();
                let o = node.val.take();

                return o;
            }
        }
        return None;
    }

    //展示链表中的元素
    fn show(&self) {
        let mut node = self.head.clone();
        while node.is_some() {
            if let Some(n) = node {
                n.borrow().show();
                node = n.clone().borrow().next.clone()
            }
        }
        println!();
    }
}

pub fn hello_linkedlist() {
    let mut linked_list = LinkedList::new();
    for i in 0..10 {
        linked_list.insert_last(i);
    }

    linked_list.show();
    for i in 0..10 {
        linked_list.insert_head(i);
    }
    linked_list.show();
    for _ in 0..5 {
        let v = linked_list.remove_last();
        if let Some(val) = v {
            println!("移除最后一个元素:{}", val);
        }
    }

    linked_list.show();
}
